home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource5 / 332_01 / pressup.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-30  |  17.6 KB  |  834 lines
  1. /*----------------------------------------------------*- Fundamental -*-
  2.  
  3. Facility:        pressup
  4.  
  5. File:            pressup.c
  6.  
  7. Associated files:    - (none)
  8.  
  9. Description:        Strategy board game
  10.  
  11. Portability:        [A Thulin:]
  12.  
  13.             Edited to conform to X/Open Portability
  14.             Guide, ed. 3, 1988.
  15.  
  16. Author:            Prof. Steve Ward
  17.             Director, Real-Time Systems Group
  18.             MIT Lab for Computer Science
  19.             Cambridge, Massachussetts, 02139
  20.  
  21. Editors:        Leor Zolman
  22.  
  23.             Anders Thulin
  24.             Rydsvagen 288
  25.             S-582 50 Linkoping
  26.             SWEDEN
  27.  
  28. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  29.  
  30. Edit history :
  31.  
  32. Vers  Ed   Date        By                Comments
  33. ----  ---  ----------  ----------------  -------------------------------
  34.  1.0    0  19xx-xx-xx  Steve Ward
  35.  1.1    1  19xx-xx-xx  Leor Zolman
  36.  1.2    2  1989-10-25  Anders Thulin     Changed to curses-oriented
  37.                          user interface.
  38.  
  39. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  40.  
  41. /*---  Configuration options:
  42.  
  43. /* - - Configuration options:  - - - - - - - - - - - - - - - - - - - - - - */
  44.  
  45. /*
  46.  *  Compile-time environment:
  47.  *
  48.  *    ANSI        ANSI C
  49.  *    BSD        BSD Unix, SunOS 3.5
  50.  *    SV2        AT&T UNIX System V.2
  51.  *    XPG3        X/Open Portability Guide, ed. 3
  52.  *    ZTC205        Zortech C 2.05
  53.  *
  54.  *  If you have an ANSI C conforming compiler, you only need to define 
  55.  *  `ANSI'. If you don't, choose one of the other definitions.  Don't
  56.  *  forget to define BEEP() correctly.
  57.  *
  58.  */
  59.  
  60. #define    ANSI        0    
  61. #define BSD        0
  62. #define    SV2        0
  63. #define XPG3        0
  64. #define ZTC205        1
  65.  
  66. /*
  67.  *  Run-time environment:
  68.  *
  69.  *  BEEP()    See 'comments' below
  70.  *
  71.  */
  72.  
  73. #define    BEEP()    beep()
  74.  
  75. /* - - end of configuration options - - - - - - - - - - - - - - - - - - - */
  76.  
  77. #if ANSI
  78. # include <ctype.h>
  79. # include <curses.h>
  80. # include <stdio.h>
  81. # include <stdlib.h>
  82.   extern int getopt(int argc, char **argv, char *optstring);
  83.   extern int   optind;
  84.   extern char *optarg;
  85. #endif
  86.  
  87. #if BSD
  88. # include <ctype.h>
  89. # include <curses.h>
  90. # include <stdio.h>
  91.   extern int getopt();
  92.   extern int   optind;
  93.   extern char *optarg;
  94.   extern long  strtol();
  95. # define EXIT_FAILURE    1
  96. # define EXIT_SUCCESS    0
  97. #endif
  98.  
  99. #if SV2
  100. # include <ctype.h>
  101. # include <curses.h>
  102.   extern int getopt();
  103.   extern int   optind;
  104.   extern char *optarg;
  105.   extern long  strtol();
  106. # define EXIT_FAILURE    1
  107. # define EXIT_SUCCESS    0
  108. #endif
  109.  
  110. #if XPG3
  111. # include <ctype.h>
  112. # include <curses.h>
  113. # include <stdio.h>
  114. # include <stdlib.h>
  115.   extern int getopt();
  116.   extern int   optind;
  117.   extern char *optarg;
  118. #endif
  119.  
  120. #if ZTC205
  121. # include <ctype.h>
  122. # include <curses.h>
  123. # include <stdio.h>
  124.   extern int getopt();
  125.   extern int   optind;
  126.   extern char *optarg;
  127. # define EXIT_FAILURE    1
  128. # define EXIT_SUCCESS    0
  129. # define strtol(str, ptr, base)    ((base) == 0 ? atoi(str) : (-1))
  130. #endif
  131.  
  132. /*--- Comments on known problems: -----------------------------------------
  133.  
  134. curses
  135.  
  136.     Some older implementations of curses may not have the beep()
  137.     call. On these systems, you may be able to define BEEP() as
  138.     addch(0x07), or perhaps fputc(0x07, stderr) or something
  139.     similar.
  140.  
  141.     If you cannot do a beep, try a screen flash
  142.  
  143.     If you cannot do either, just define BEEP to be empty.
  144.  
  145. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  146.  
  147.  
  148. /*  'man-page' based on comments in original program:
  149.  
  150. pressup(6)                    pressup(6)
  151.  
  152. NAME
  153.     pressup
  154.  
  155. SYNOPSIS
  156.     pressup [ -f ] [ -d depth ] [ -b ]
  157.  
  158.  
  159. DESCRIPTION
  160.  
  161.     The game of Press-Ups is played as follows: The board is a n by
  162.     n array of pegs, each of which is standing up at the start of
  163.     the game.  Pegs come in 3 colors: red (yours), blue (the
  164.     machine's), and white (periods, actually; they're neutral.)
  165.  
  166.     The first player to move must `push down' a neutral peg. 
  167.     Thereafter, players take turns pushing down pegs, where each peg
  168.     pushed must be adjacent to the last one pushed. 
  169.  
  170.     The player moves the cursor to the wanted peg by using the
  171.     `standard' keys h, j, k, and l to move right, down, up and left
  172.     respectively.  The player then presses the selected key by 
  173.     pressing the space bar.  If an illegal key has been selected,
  174.     the program beeps or flashes the screen.
  175.  
  176.     As soon as a player gets all of his pegs down, he wins.  When
  177.     there are no more legal moves to play, the player with the most
  178.     of his own colored pegs down is the winner. 
  179.  
  180.  
  181. OPTIONS
  182.  
  183.     -f    The program makes the first move
  184.  
  185.     -d depth
  186.         Set search-depth to 'depth'. Default is 3.
  187.  
  188.     -b    Show evaluation of position (negative numbers means
  189.         the player has the upper hand,  positive that
  190.         the program thinks it's winning)
  191.  
  192. CAVEAT
  193.  
  194.     Watch out...at search depths of 6 or more, this program plays a
  195.     mean game!!!
  196.  
  197. AUTHOR
  198.  
  199.     Steve Ward wrote the original program.  Leor Zolman and later
  200.     Anders Thulin edited it.
  201.  
  202. BUGS
  203.  
  204.     (A. Thulin:)
  205.  
  206.     Some players may feel that the keys chosen for cursor movement
  207.     (h,j,k and l) are less than intuitive to use. The reason they were
  208.         chosen is that many other UNIX-games like hack, nethack,
  209.         rogue and vi use these keys for the same purpose. It is left as
  210.         an exercise to change it to handle arrow keys with curses.
  211.     Complaints to /dev/null.
  212. */
  213.  
  214. #define    HDR        " Pressup 1.2 "
  215.  
  216. /*  Display definitions - depend on 24 x 80 screen:  */
  217.  
  218. #define    HDRX        1    /* HDR - Version line */
  219. #define    HDRY        1
  220.  
  221. #define    BOARDX        1    /* Upper left corner of board    */
  222. #define    BOARDY        3
  223.  
  224. #define    STATUSX        1    
  225. #define    STATUSY        15
  226.  
  227. #define    DEPTHX        30
  228. #define    DEPTHY        BOARDY
  229.  
  230. #define    SCOREX        DEPTHX
  231. #define    SCOREY        DEPTHY+2
  232.  
  233. #define    HELPX        DEPTHX
  234. #define    HELPY        SCOREY+2
  235.  
  236. #define    STARTX        DEPTHX
  237. #define    STARTY        HELPY+2
  238.  
  239. #define    EVALX        DEPTHX
  240. #define    EVALY        STARTY+2
  241.  
  242. /*  Game definitions:  */
  243.  
  244. #define MAX_SIDE    13    /* Max dimension of board    */
  245.  
  246. #define HISFIRST (Side*2+1)    /* His best first move    */
  247. #define MYFIRST (Side+Side/2-1) /* My best first move    */
  248.  
  249. #define BACKSP     0x08
  250.  
  251. int    BestMove;    /* Returned by search        */
  252. char    BFlag;        /* Debugging flag        */
  253. int    Depth;        /* Search depth (default = 3)    */
  254. char    FFlag;        /* -f option: machine goes first */
  255. int    Helpflag;
  256. int    Side = 7;    /* Current side of board    */
  257. char    Startflag;    /* True on first move only */
  258.  
  259. char   *image;
  260.  
  261. int     Adj[16] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1 };
  262.  
  263. typedef struct {
  264.   char board[MAX_SIDE*MAX_SIDE];
  265.   int  star;
  266.   char red;
  267.   char blue;
  268. } BBOARD;
  269.  
  270. BBOARD initb;
  271. BBOARD master, savebd;
  272.  
  273. /*  Local routines:  */
  274.  
  275. #if __STDC__ != 0
  276.  void asknew(void);
  277.  void boardcopy(BBOARD *p1, BBOARD *p2);
  278.  int  CheckWin(BBOARD *bp);
  279.  void dmove(int n);
  280.  int  getmove(void);
  281.  int  Help(void);
  282.  void mmove(BBOARD *bp, int n);
  283.  void pboard(BBOARD *bp);
  284.  void print_square(BBOARD *bp, int row, int col, int invert);
  285.  int  search(BBOARD *bp, int ddepth, int who, int alpha, int beta);
  286. #else
  287.  void asknew();
  288.  void boardcopy();
  289.  int  CheckWin();
  290.  void dmove();
  291.  int  getmove();
  292.  int  Help();
  293.  void mmove();
  294.  void pboard();
  295.  void print_square();
  296.  int  search();
  297. #endif
  298.  
  299. /*
  300.  *  Routine:        asknew
  301.  *
  302.  *  Description:    Ask user if he wants a new game.  Quit if not.
  303.  *
  304.  */
  305.  
  306. void asknew()
  307. {
  308.   addstr("Another game? ");    
  309.   refresh();
  310.   if (toupper(getchar()) != 'Y') {
  311.     move(LINES-1, 0);
  312.     refresh();
  313.     endwin();
  314.     exit(EXIT_SUCCESS);
  315.   }
  316. }
  317.  
  318. /*
  319.  *  Routine:        boardcopy
  320.  *
  321.  *  Description:    Copy a board.
  322.  *
  323.  *  Note:        Originally copied each element of p1 to p2
  324.  *            by hand, probably because C didn't allow
  325.  *            assignments of whole structs.  It does now.
  326.  *
  327.  */
  328.  
  329. void boardcopy(p1, p2)
  330. BBOARD *p1, *p2;
  331. {
  332.   *p2 = *p1;
  333. }
  334.  
  335. /*
  336.  *  Routine:        Checkwin
  337.  *
  338.  *  Description:    Check if any side has won, and return 1 if so.
  339.  *            Also print the appropriate text. If no-one has
  340.  *            won, return 0.
  341.  *
  342.  */
  343.  
  344. int CheckWin(bp)
  345. BBOARD *bp;
  346. {
  347.   int i;
  348.   i = search(bp, 1, 1, -32000, -32000);
  349.   if (BestMove >= 0) return 0;
  350.  
  351.   move(BOARDY+Side+3, STATUSX);
  352.  
  353.   if (i>0) {
  354.     addstr("I win! ");
  355.   }
  356.   if (i<0) {
  357.     addstr("You win! ");
  358.   }
  359.   if (i==0) {
  360.     addstr("Tie game! ");
  361.   }
  362.   return 1;
  363. }
  364.  
  365. /*
  366.  *  Routine:        dmove
  367.  *
  368.  *  Description:    display move #n
  369.  *
  370.  */
  371.  
  372. void dmove(n)
  373. int n;
  374. {
  375.   mmove(&master,n);
  376.   pboard(&master);
  377.   boardcopy(&master,&savebd);
  378. }
  379.  
  380. /*
  381.  *  Routine:        getmove
  382.  *
  383.  *  Description:    Get player's next move, and return it as an
  384.  *            integer (row*size + col).
  385.  *
  386.  *            Negative move indicates a quit.
  387.  *
  388.  */
  389.  
  390. int getmove()
  391. {
  392.   int chg_flag;        /* User changed coordinates */
  393.   int cmd;        /* command char from user */
  394.   int dr, dc;        /* offset from previous move */
  395.   int m;        /* selected move */
  396.   int move_selected;    /* TRUE when user has selected a legal move */
  397.   int row, col;        /* current board coordinate */
  398.   int rd,  cd;        /* offset to new board coordinate */
  399.   int star;        /* previous move (< 0 if no previous move) */
  400.  
  401.   star = master.star;
  402.  
  403.   /*  1.  Prompt for move:  */
  404.  
  405.   move(BOARDY + Side + 1, STATUSX); 
  406.   addstr("Select and press peg ... ");
  407.  
  408.   /*  2.  Loop until a legal square has been selected:  */
  409.  
  410.   if (star >= 0) {    /* start at previous move */
  411.     row = star/Side;
  412.     col = star%Side;
  413.   } else {        /* else start in the middle */
  414.     col = row = Side/2;
  415.   }
  416.  
  417.   move_selected = FALSE; chg_flag = TRUE;
  418.   while (!move_selected) {
  419.  
  420.     if (chg_flag) {    /* avoid unneccessary updates */
  421.       print_square(&master, row, col, TRUE);
  422.       refresh();
  423.       chg_flag = FALSE;
  424.     }
  425.  
  426.     cmd = getch();
  427.     if (islower(cmd)) {
  428.       cmd = toupper(cmd);
  429.     }
  430.  
  431.     rd = cd = 0;
  432.     switch(cmd) {
  433.       default:        /* Unknown command  */
  434.         BEEP();
  435.         break;
  436.  
  437.       case ERR:        /* Problem or non-blocking getch() */
  438.     break;        
  439.  
  440.       case ' ':            /* select current position */
  441.         m  = row*Side + col;
  442.         if (star < 0) {     /* first move */
  443.           if (master.board[m] == 0) {
  444.             move_selected = TRUE;
  445.           } else {
  446.             BEEP();
  447.           }
  448.         } else {
  449.           dr = abs(row - star/Side);
  450.           dc = abs(col - star%Side);
  451.           if (master.board[m] < 3 && dr < 2 && dc < 2) {
  452.             move_selected = TRUE;
  453.           } else {
  454.             BEEP();
  455.           }
  456.         }
  457.         break;
  458.  
  459.       case 'H':        /* move left  */
  460.         if (col == 0) {
  461.           BEEP();
  462.         } else {
  463.           cd = -1;
  464.         }
  465.     break;
  466.  
  467.       case 'J' :
  468.         if (row == Side-1) {
  469.           BEEP();
  470.         } else {
  471.           rd = 1;
  472.         }     
  473.         break;
  474.  
  475.       case 'K' :
  476.         if (row == 0) {
  477.           BEEP();
  478.         } else {
  479.           rd = -1;
  480.         }
  481.         break;
  482.  
  483.       case 'L':        /* move right */
  484.         if (col == Side-1) {
  485.           BEEP();
  486.         } else {
  487.           cd = 1;
  488.         }
  489.     break;
  490.  
  491.       case 'Q':        /* user wants to quit */
  492.         m = -1;
  493.         move_selected = TRUE;
  494.         break;
  495.  
  496.       case 'Z':        /* He wants help ... */
  497.         m = Help();
  498.         move_selected = TRUE;
  499.         break;
  500.     }
  501.  
  502.     if (rd != 0 || cd != 0) {
  503.       print_square(&master, row, col, FALSE);
  504.       row += rd; col += cd;
  505.       chg_flag = TRUE;
  506.     }
  507.   }
  508.  
  509.   return m;
  510. }
  511.  
  512. /*
  513.  *  Routine:        Help
  514.  *
  515.  *  Description:    Give the poor soul some badly needed assistance
  516.  *
  517.  */
  518.  
  519. int Help()
  520. {
  521.   move(BOARDY+Side+1, STATUSX);
  522.   addstr("I'm thinking for you...");
  523.   Helpflag = 1;
  524.   search(&master,Depth,-1,-32000,-32000);
  525.   return BestMove;
  526. }
  527.  
  528. /*
  529.  *  Routine:        main
  530.  *
  531.  *  Description:    ...
  532.  *
  533.  */
  534.  
  535. int main(argc, argv)
  536. int   argc;
  537. char *argv[];
  538. {
  539.   int   ch;        /* option char from argv    */
  540.   int    errflag;    /* TRUE if something went wrong in arg parsing */
  541.   int   i,j;
  542.  
  543.   FFlag  = BFlag = 0;
  544.   image = ".rbXRB";
  545.   Depth = 3;
  546.   errflag = FALSE;
  547.  
  548.   /* Do getopt instead:  */
  549.  
  550.   while ((ch =getopt(argc, argv, "bd:f")) != EOF) {
  551.     switch(ch) {
  552.       default :        /* unknown value returned from getopt() */
  553.         fprintf(stderr, "fatal: unknown value returned from getopt(): %x\n",
  554.                         ch);
  555.         exit(EXIT_FAILURE);
  556.  
  557.       case '?':        /* unknown option letter - errmsg already printed */
  558.         errflag = TRUE;
  559.         break;
  560.  
  561.       case 'b':
  562.         BFlag++;
  563.         break;
  564.  
  565.       case 'd':        /* depth of search tree */
  566.         Depth = (int) strtol(optarg, (char **)0, 0);
  567.         break;
  568.  
  569.       case 'f':
  570.         FFlag++;
  571.         break;
  572.     }
  573.   }
  574.   
  575.   if (optind < argc) {
  576.     fprintf(stderr, "unknown argument -- '%s'\n", argv[optind]);
  577.     errflag = TRUE;
  578.   }
  579.  
  580.   if (errflag) {
  581.     fprintf(stderr, "usage: pressup [-b] [-d depth] [-f]\n");
  582.     exit(EXIT_FAILURE);
  583.   }
  584.  
  585.  
  586.   initscr();
  587.   cbreak();
  588.   noecho();
  589.  
  590. ngame:
  591.   Startflag = 1;
  592.   Helpflag = 0;
  593.   for (i=0; i<(Side*Side); i++) initb.board[i] = 0;
  594.   for (j=1; j<(Side-1); j++) {
  595.     initb.board[j] = 1;
  596.     initb.board[(Side*Side-1)-j] = 1;
  597.     initb.board[Side*j] = 2;
  598.     initb.board[Side*j + Side-1] = 2;
  599.   };
  600.   initb.star = -1; initb.red = 0; initb.blue = 0;
  601.  
  602.   boardcopy(&initb, &master);
  603.   pboard(&master);
  604.   boardcopy(&master, &savebd);
  605.  
  606.   for(;;) {
  607.     if (FFlag) {
  608.       FFlag = 0;
  609.       goto Mine;
  610.     }
  611.     if (CheckWin(&master)) {
  612.       asknew();
  613.       goto ngame;
  614.     }
  615.     i = getmove();
  616.     if (i < 0) {    
  617.       move(BOARDY+Side+3, STATUSX);
  618.       addstr("You quit! ");
  619.       asknew();
  620.       goto ngame;
  621.      }
  622.     dmove(i);
  623.     if (CheckWin(&master)) {
  624.       asknew();
  625.       goto ngame;
  626.      }
  627. Mine:
  628.     move(BOARDY+Side+1, STATUSX);
  629.     addstr("I'm thinking...                ");
  630.     i = search(&master, Depth, 1, -32000, -32000);
  631.     if (BFlag) {
  632.       move(EVALX, EVALY); printw("Pos. eval = %4d", i); 
  633.     }
  634.     dmove(BestMove);
  635.     if (i > 500) {
  636.       move(STATUSY+1, STATUSX); addstr("I've got you!"); 
  637.     }
  638.     if (i < -500) {
  639.       move(STATUSY+1, STATUSX); addstr("You've got me!"); 
  640.     }
  641.   }
  642.  
  643.   /*NOTREACHED*/  /* asknew() exits */
  644. }
  645.  
  646. /*
  647.  *  Routine:        mmove
  648.  *
  649.  *  Description:    Make a move
  650.  *
  651.  */
  652.  
  653. void mmove(bp,n)
  654. BBOARD *bp;
  655. int     n;
  656. {
  657.   int type;
  658.   type = bp->board[n] += 3;
  659.   if (type == 4) bp->red++;
  660.   else if (type == 5) bp->blue++;
  661.   bp->star = n;
  662. }
  663.  
  664. /*
  665.  *  Routine:        pboard
  666.  *
  667.  *  Description:    Update screen with new board, status, and everything.
  668.  *
  669.  */
  670.  
  671. void pboard(bp)
  672. BBOARD *bp;
  673. {
  674.   int row, col;        /*  Board coordinates */
  675.  
  676.   /*  1.  Program name and version:  */
  677.  
  678.   move(HDRY, HDRX); addstr(HDR);
  679.  
  680.   /*  2.  Board:  */
  681.  
  682.   for (row=0; row<Side; row++) {
  683.     for (col=0; col<Side; col++) {
  684.       print_square(bp, row, col, FALSE);
  685.     }
  686.   }
  687.  
  688.   /*  3.  Print score, search depth and other info:  */
  689.  
  690.   move(DEPTHY, DEPTHX);
  691.   printw("Search Depth: %2d moves", Depth);
  692.  
  693.   move(SCOREY, SCOREX);
  694.   printw("Score:    Blue (me) %2d,   Red (you)  %2d", master.blue, master.red);
  695.  
  696.   if (Helpflag) {
  697.     move(HELPY, HELPX);
  698.     addstr("You've had help!");
  699.   }
  700.   
  701.   if (Startflag) {
  702.     move(STARTY, STARTX);
  703.     addstr(FFlag ? "I go first" : "You go first");
  704.     Startflag = 0;
  705.   }
  706. }
  707.  
  708. /*
  709.  *  Routine:        print_square
  710.  *
  711.  *  Description:    Print a square on the given board. 
  712.  *
  713.  */
  714.  
  715. void print_square(bp, row, col, invert)
  716. BBOARD *bp;
  717. int     row;
  718. int     col;
  719. int     invert;
  720. {
  721.   int    n;    /* internal coordinate */
  722.  
  723.   move(BOARDY+row, BOARDX+3*col);    /* Each square is 3 char wide */
  724.   
  725.   if (invert) {
  726.     standout();
  727.   }
  728.  
  729.   n = row*Side + col;      
  730.   if (bp->star == n) {
  731.     addstr(" * ");
  732.   } else {
  733.     printw(" %c ", image[bp->board[n]]);
  734.   }
  735.  
  736.   if (invert) {
  737.     standend();
  738.   }
  739.  
  740.  /*
  741.   *  Leave cursor *on* square. 
  742.   *  This is quite good for systems with line cursors. Non-blinking
  743.   *  block cursors give a rather odd impression, though.
  744.   *
  745.   */
  746.  
  747.   move(BOARDY+row, BOARDX+3*col+1);
  748. }
  749.  
  750. /*
  751.  *  Routine:        search
  752.  *
  753.  *  Description:    Alpha-beta pruning search
  754.  *
  755.  *            Put best move for 'who' into BestMove. Return
  756.  *            estimated strength of position.
  757.  *
  758.  */
  759.  
  760. int search (bp,ddepth,who,alpha,beta)
  761. BBOARD *bp;
  762. int ddepth;
  763. int who;
  764. int alpha;
  765. int beta;
  766. {
  767.   int i,j,k;
  768.   int myalpha,hisalpha;
  769.   int best;
  770.   int num;
  771.   int bestmove, ii, jj, n;
  772.   int SavStar;
  773.   int SavBlue;
  774.   int SavRed;
  775.   int Save;
  776.   char moves[9];
  777.  
  778.   best = -32000;
  779.   SavStar = bp->star;
  780.   SavBlue = bp->blue;
  781.   SavRed  = bp->red;
  782.   BestMove = -1;        /* No best move yet...    */
  783.  
  784.   if (SavStar < 0) {        /* special case opening moves    */
  785.     BestMove = HISFIRST;
  786.     if (who > 0) BestMove = MYFIRST;
  787.     return 0;
  788.   };
  789.  
  790.   if (!ddepth--)
  791.     return(who * (bp->blue - bp->red));
  792.  
  793.   if (bp->blue == (Side*2-4) || bp->red == (Side*2-4))
  794.     return(who*(bp->blue - bp->red)*1000);
  795.  
  796.   /* alpha-beta pruning   */
  797.   if (who>0) {
  798.     myalpha = bp->blue; hisalpha = bp->red; 
  799.   } else {
  800.     myalpha = bp->red; hisalpha = bp->blue; 
  801.   }
  802.   myalpha += ddepth;  /* Most optimistic estimate. */
  803.   if (myalpha > (Side*2-4)) myalpha = (Side*2-4);
  804.   if (myalpha == (Side*2-4)) myalpha = 1000*(myalpha-hisalpha);
  805.   else myalpha -= hisalpha;
  806.   if (myalpha <= alpha) return best;
  807.  
  808.   k = bp->star;
  809.   i = k%Side;
  810.   j = k/Side;
  811.   num = 0;
  812.   for (n=0; n<8; n++) {        /* Try squares 'around' last move */
  813.     if ((ii = i+Adj[n+n]) < 0 || ii >= Side) continue;
  814.     if ((jj = j+Adj[n+n+1]) < 0 || jj >= Side) continue;
  815.     moves[num] = jj*Side + ii;
  816.     if (bp->board[moves[num]] < 3) num++; 
  817.   }
  818.   if (num == 0) return(who*(bp->blue - bp->red)*1000);
  819.   bestmove = moves[0];
  820.   for (i=0; i<num; i++) {
  821.     Save = bp->board[moves[i]];
  822.     mmove(bp,moves[i]);
  823.     k = -search(bp,ddepth,-who,beta,alpha);
  824.     bp->board[moves[i]] = Save;
  825.     bp->blue = SavBlue; bp->red = SavRed; bp->star = SavStar;
  826.     if (k > alpha) alpha = k;
  827.     if (k > best) { best = k; bestmove = moves[i]; }
  828.     if (k>100) break;
  829.   }
  830.   BestMove = bestmove;
  831.   return best;
  832. }
  833.  
  834.